class Solution {
public:
    /*
        设dp[i]位以i位置结尾的最长等差数列，那么由等差数列的性质，
        为了可以直接得出要使以i位置结尾的元素数列最长，它就应该跟在值为arr[i] - diff的元素后
        为了可以快速得到以值为（arr[i] - diff）结尾的最长等差数列，我们可以利用哈希表来存储
    */
    
    int longestSubsequence(vector<int>& arr, int difference) {
        int ret = 1;
        int n = arr.size();
        unordered_map<int, int> hash;
        hash[arr[0]] = 1;

        //直接在哈希表里动态规划
        for (int i = 1; i < n; ++i)
        {
            //arr[i] - arr[j] = diff
            //arr[j] = arr[i] - diff
            int tmp = arr[i] - difference;

            //如果不存在，则无法与之前的元素构成等差序列，长度为1
            if (!hash.count(tmp))
                hash[arr[i]] = 1;
            else    //存在，就可以和前面的元素构成等差数列
            {
                hash[arr[i]] = 1 + hash[tmp];
                ret = max(ret, hash[arr[i]]);
            }
        }
 
        return ret;
    }


    //超时
    // int longestSubsequence(vector<int>& arr, int difference) {
    //     int ret = 0;
    //     int n = arr.size();
    //     vector<int> dp(n, 1);

    //     for (int i = 1; i < n; ++i)
    //     {
    //         for (int j = i - 1; j >= 0; --j)
    //         {
    //             if (arr[i] - arr[j] == difference)
    //                 dp[i] = max(dp[i], 1 + dp[j]);
    //         }
    //         ret = max(ret, dp[i]);
    //     }

    //     return ret;
    // }
};